import java.util.Stack;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * 输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否可能为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如序列1,2,3,4,5是某栈的压入顺序，序列4,5,3,2,1是该压栈序列对应的一个弹出序列，但4,3,5,1,2就不可能是该压栈序列的弹出序列。
 * 1. 0<=pushV.length == popV.length <=1000
 * 2. -1000<=pushV[i]<=1000
 * 3. pushV 的所有数字均不相同
 * User: 徐海涛
 * Date: 2022-01-15
 * Time: 10:14
 */
public class TestDemo2 {
    //栈的弹出压入序列
    public boolean IsPopOrder(int[] pushA, int[] popA) {
        Stack<Integer> stack = new Stack<>();

        int j = 0;
        for (int i = 0; i < pushA.length; i++) {
            stack.push(i);//遍历pushA并且入栈
            while (j < popA.length && !stack.empty() && stack.peek() == popA[j]) {
                stack.pop();
                j++;
            }
        }
        return stack.empty();
    }

    public boolean isValid(String s) {
        Stack<Character> stack = new Stack<>();

        for (int i = 0; i < s.length(); i++) {
            char ch = s.charAt(i);
            if (ch == '(' || ch == '[' || ch == '{') {
                //如果是左括号 直接入栈
                stack.push(ch);
            } else {
                //遇到了右括号
                if (stack.empty()) {
                    //右括号多
                    System.out.println("右括号多");
                    return false;
                }
                char top = stack.peek();//哪个左括号
                if (top == '{' && ch == '}' || top == '[' && ch == ']' || top == '(' && ch == ')') {
                    stack.pop();
                } else {
                    //左右括号不匹配
                    System.out.println("左右括号不匹配");
                    return false;
                }
            }
        }
        if (!stack.empty()) {
            //左括号多
            System.out.println("左括号多");
            return false;
        }
        return true;

    }


    public static void main1(String[] args) {
        MyStack stack = new MyStack();
        stack.push(1);
        stack.push(2);
        stack.push(3);
        stack.push(4);
        System.out.println(stack.pop());
        System.out.println(stack.peek());
        System.out.println(stack.isEmpty());
    }

    public static void main6(String[] args) {
        Stack<Integer> stack = new Stack<>();
        stack.push(1);//push入栈
        stack.push(2);
        stack.push(3);
        stack.push(4);
        stack.push(5);
        System.out.println(stack);
        System.out.println(stack.pop());//弹出栈顶的元素并删除5
        System.out.println(stack.peek());//获取栈顶元素，但是不删除
        System.out.println(stack.empty());
        System.out.println("======");
        System.out.println(stack.isEmpty());
        System.out.println();
    }



    public int evalRPN(String[] tokens) {//逆波兰表达式，后缀表达式
        Stack<Integer> stack = new Stack<>();
        for (int i = 0; i < tokens.length; i++) {
            String val = tokens[i];
            if (isOperation(val) == false) {
                //如果不是运算符
                stack.push(Integer.parseInt(val));
            } else {
                //到底啥运算符？？？？
                int num2 = stack.pop();
                int num1 = stack.pop();
                switch (val) {
                    case "+":
                        stack.push(num1 + num2);
                        break;
                    case "-":
                        stack.push(num1 - num2);
                        break;
                    case "*":
                        stack.push(num1 * num2);
                        break;
                    case "/":
                        stack.push(num1 / num2);
                        break;
                }
            }
        }
        return stack.pop();
    }

    private boolean isOperation(String x) {
        if (x.equals("+") || x.equals("-") || x.equals("*") || x.equals("/")) {
            return true;
        }
        return false;
    }

    public static int calPoints(String[] ops) {
        Stack<Integer> stack = new Stack<>();
        int sum = 0;//sum记录总分
        for (int i = 0; i < ops.length; i++) {
            //c表示前一次的分无效，并将其从中移除
            if("c".equals(ops[i])) {
                sum = sum - stack.pop();
            }else if("D".equals(ops[i])) {
                //D表示新获得的分是前一次的两倍
                int n = stack.peek()*2;
                sum = sum + n;
                stack.push(n);//新的得分入栈
            }else if("+".equals(ops[i])) {
                //+表示本回合得分为前两次总分的和
                int n = stack.pop();
                int m = stack.peek() + n;
                sum = sum + m;
                //由于把n删除了 要从新入栈
                stack.push(n);
                stack.push(m);
            }else {
                int n = Integer.parseInt(ops[i]);//1 2 3 4 5 6 123
                sum = sum + n;
                stack.push(n);
            }
        }
        return sum;
    }

    public static void main(String[] args) {
        String[] str = {"5","2","C","D","+"};
        System.out.println(calPoints(str));
    }

    public boolean backspaceCompare(String s, String t) {
        Stack<String> stack = new Stack<>();
        Stack<String> stack1 = new Stack<>();
        char[] chars= s.toCharArray();
        char[] chars1 = t.toCharArray();
        for (int i = 0; i < s.length(); i++) {
            if(chars[i]=='#') {
                if(!stack.empty()) {
                    stack.pop();
                }
            }else {
                stack.push(chars[i]+"");
            }
            for (int j = 0; j < t.length(); j++) {
                if(chars1[j]=='#') {
                    if(!stack1.empty()){
                        stack1.pop();
                    }
                }else {
                    stack1.push(chars1[i]+"");
                }
            }
        }
        while (!stack.isEmpty() && !stack1.isEmpty()) {
            if (stack.peek() != stack1.peek()) return false;
            stack.pop();
            stack1.pop();
        }
        return stack.isEmpty() && stack1.isEmpty();
    }
}
